class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right



class Solution(object):
    def widthOfBinaryTree(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        d_min = {}
        d_max = {}

        def search(node, depth, val):
            if depth not in d_min:
                d_min[depth] = val
                d_max[depth] = val
            else:
                d_min[depth] = min(d_min[depth], val)
                d_max[depth] = max(d_max[depth], val)
            if node.left:
                search(node.left, depth + 1, 2 * val + 1)
            if node.right:
                search(node.right, depth + 1, 2 * val + 2)

        search(root, 0, 0)
        max_val = 0
        for depth in d_min:
            max_val = max(max_val, d_max[depth] - d_min[depth] + 1)
        return max_val
